package util;

import java.math.BigDecimal;
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Random;

public class Util {
	public static final BigInteger TWO = new BigInteger("2");
	public static final BigInteger ONE = new BigInteger("1");
	public static final BigDecimal two = new BigDecimal("2");
	
	private static Random rnd = null;
	
	public static Random getRnd()
	{
		if(rnd == null) rnd = new Random();
		return rnd;
	}
	
	public static ArrayList<Integer> getSmooth(int x)
	{
		ArrayList<Integer> list = new ArrayList<Integer>();
		for(int i = 1; i < x; ++i)
			if(jeProst(i))
				list.add((int)(Math.pow(i, Math.floor(Math.log(x) / Math.log(i)))));
		return list;
	}
	
	public static BigInteger biSqrt(BigInteger x)
	{
		//BigInteger g = x.divide(TWO);
		BigDecimal m = new BigDecimal(x);
		BigDecimal X = new BigDecimal(x);
		m = m.divide(two);
		
		for(int i = 0; i < 20; ++i)
		{
			BigDecimal sq = m.multiply(m);
			int comp = sq.compareTo(X);
			
			if(comp == 0) return m.toBigInteger();
			
			if(comp < 0)
			{
				m = m.add(m.divide(two));
			}
			else
			{
				m = m.subtract(m.divide(two));
			}
		}
		
		BigInteger n = m.toBigInteger();
		if(x.compareTo(n.multiply(n)) < 0)
			return n.subtract(ONE);
		else
			return n;
	}
	
	public static BigInteger biSqrt2(BigInteger x)
	{
		BigInteger step = x.divide(TWO);
		step = step.divide(TWO);
		BigInteger n = x.divide(TWO);
		
		while(step.compareTo(ONE) > 0)
		{
			BigInteger sq = n.multiply(n);
			int comp = sq.compareTo(x); 
			if(comp == 0) 
				return n;
			else if(comp < 0)
				n = n.add(step);
			else
				n = n.subtract(step);
			
			if(step.compareTo(ONE) > 0)
				step = step.divide(TWO);
		}
		
		if(x.compareTo(n.multiply(n)) < 0)
			return n.subtract(ONE);
		else
			return n;
	}
	
	public static int sqrt(int x)
	{
		int g = x / 2;
		int step = g / 2;
		
		while(g * g > x || (g * g <= x - g))
		{
			if(g * g == x) return g;
		
			if(g * g > x)
				g -= step;
			else
				g += step;
			
			if(step > 1)
				step /= 2;
			else
				step = 1;
		}
		
		return g;
	}
	
	public static BigInteger sqrtBi(BigInteger x)
	{
		BigInteger g = x.divide(TWO);
		BigInteger step = g.divide(TWO);
		
		while(x.compareTo(g.multiply(g)) < 0 || (g.multiply(g).compareTo(x.subtract(g))) <= 0)
		{
			int comp = g.multiply(g).compareTo(x);
			if(comp == 0) return g;
			
			if(comp > 0)
				g = g.subtract(step);
			else
				g = g.add(step);
			
			if(step.compareTo(ONE) > 0)
				step = step.divide(TWO);
			else
				step = ONE;
		}
		
		return g;
	}
	
	public static int nzd(int a, int b) {
		if (b == 0)
			return a;
		return nzd(b, a % b);
	}
	
	public static boolean jeProst(int broj){
		if(broj == 3 || broj == 7)
			return true;
		if(broj % 2 == 0 || broj % 3 == 0 || broj % 7 == 0)
			return false;
		int koren = (int) Math.sqrt(broj);
		for(int i = 2; i <= koren; i++){
			if(broj % i == 0)
				return false;
		}
		return true;
	}
	
	public static int modPowI(int base, int exp, int mod)
	{
		return BigInteger.valueOf(base).modPow(BigInteger.valueOf(exp), BigInteger.valueOf(mod)).intValue();
	}
	
	public static long modPowL(long base, long exp, long mod)
	{
		return BigInteger.valueOf(base).modPow(BigInteger.valueOf(exp), BigInteger.valueOf(mod)).longValue();
	}
	
	public static void main(String args[])
	{
		System.out.println(sqrtBi(new BigInteger("16")));
		System.out.println(sqrtBi(new BigInteger("25")));
		System.out.println(sqrtBi(new BigInteger("64")));
		System.out.println(sqrtBi(new BigInteger("12345")));
		
		System.out.println(sqrt(16));
		System.out.println(sqrt(25));
		System.out.println(sqrt(64));
		System.out.println(sqrt(12345));
	}

	public static long nzd(long a, long b) {
		if (b == 0)
			return a;
		return nzd(b, a % b);
	}
	
	public static int modInvI(int n, int mod)
	{
		return BigInteger.valueOf(n).modInverse(BigInteger.valueOf(mod)).intValue();
	}
	
	public static long modInvL(long n, long mod)
	{
		return BigInteger.valueOf(n).modInverse(BigInteger.valueOf(mod)).longValue();
	}
}
